package com.ai.zuochengyun.phase01.class03;

/**
 * 前缀树
 */
public class Code04_TrieTree {

    private static class Node1 {
        public int pass;

        public int end;

        public Node1[] nexts;

        public Node1() {
            pass = 0;
            end = 0;
            // 26个小写字母
            // 0 表示走向a的路
            // 1 表示走向b的路
            // 25 表示走向z的路
            nexts = new Node1[26];
        }
    }

    // 怎么找哪条路，通过26-字符的ascii码找到下标索引


    public static class Trie1 {
        public Node1 root;

        public Trie1() {
            root = new Node1();
        }

        public void insert(String word) {
            if (word == null || word.isEmpty()) {
                return;
            }

            char[] chars = word.toCharArray();
            // 申明一个中间变量，初始位置指向root节点
            Node1 node = root;
            for (char ch: chars) {
                // 怎么找哪条路，通过当前字符减去a的ascii码找到下标索引
                int roadIndex = ch - 'a';
                // 多问一个为什么，有没有节点，没有就新建一个node节点
                if (node.nexts[roadIndex] == null) {
                    root.nexts = new Node1[26];
                }
                // node来到新加入的字符的位置
                node = root.nexts[roadIndex];
                node.pass++;
            }
            // 将整个字符加入完毕后，end++
            node.end++;
        }

        /**
         * 要考虑内存溢出风险
         * @param word
         */
        public void delete(String word) {
            if (word == null || word.isEmpty()) {
                return;
            }

            // 我先search下，看字符是否存在，如果不存在就结束
            if (search(word) == 0) {
                return;
            }

            char[] chars = word.toCharArray();
            // 申明一个中间变量，初始位置指向root节点
            Node1 node = root;
            for(char ch: chars) {
                // 怎么找哪条路，通过当前字符减去a的ascii码找到下标索引
                int roadIndex = ch - 'a';
                // 还有没有路
                if (node.nexts[roadIndex] == null) {
                    break;
                }
                node = node.nexts[roadIndex];
                // 沿途的pass减减
                node.pass--;
                if (node.pass == 0) {
                    // 如果当前节点没有字符经过了，将节点设为null，防止内存泄漏
                    node.nexts[roadIndex] = null;
                    break;
                }
            }
            node.end--;
        }

        public int search(String word) {
            if (word == null || word.isEmpty()) {
                return 0;
            }

            char[] chars = word.toCharArray();
            Node1 node = root;
            for (char ch : chars) {
                int roadIndex = ch - 'a';
                // 往下还有没有路，没有路就表示该字符不存在
                if (root.nexts[roadIndex] == null) {
                    return 0;
                }
                node = root.nexts[roadIndex];
            }
            return node.end;
        }

        public int prefixNumber(String prefix) {
            if (prefix == null || prefix.isEmpty()) {
                return 0;
            }

            char[] chars = prefix.toCharArray();
            Node1 node = root;
            for (char ch : chars) {
                int roadIndex = ch - 'a';
                // 往下还有没有路，没有路就表示该字符不存在
                if (root.nexts[roadIndex] == null) {
                    return 0;
                }
                node = root.nexts[roadIndex];
            }
            return node.pass;
        }
    }


}
